package com.spring.component.leetcode.difficult;

import com.spring.component.link.LinkFactory;
import com.spring.component.link.Node;
import com.spring.component.link.SingleNode;

/**
 * 判断单向链表是否有环及求环入口
 *
 * @ClassName: com.spring.component.leetcode.difficult.LinkHaveRing
 * @Description: 该类的功能描述
 * @version: v1.0.0
 * @author: 52879
 * @date: 2019/11/22 20:04
 */
public class LinkHaveRing {

  /**
   * 判断单向链表是否有环 一个快指针，一个慢指针，快指针每次向前2步，慢指针每次向前1步；如果有闭环，两个指针最终会指向同一个节点
   * 
   * @param singleNode
   * @return
   */
  public static boolean isHaveRing(SingleNode singleNode) {
    return runMeet(singleNode, singleNode, true) != null;
  }

  /**
   * 计算闭环切入节点
   * 1、快、慢指针都从head开始向前，快指针每次向前2步，慢指针每次向前1步
   * 2、如果有闭环，两指针会相遇；相遇后，快指针重新从head开始向前，每次1步，
   *    慢指针从相遇点开始向前，每次1步，再次相遇点就是闭环切入点
   * 
   * @param singleNode
   * @return
   */
  public static Node getRingCutPoint(SingleNode singleNode) {
    Node mettNode = runMeet(singleNode, singleNode, true);
    // 相遇后，快指针从head开始移动，慢指针从相遇点移动，再次相遇点便是闭环切入点
    return runMeet(singleNode, mettNode, false);
  }

  public static Node runMeet(Node fastSingleNode, Node slowSingleNode,
      boolean isFast) {
    Node fastNode = fastSingleNode.getNext();
    if (fastNode == null) {
      // 快指针指向了null
      return null;
    }
    if (isFast) {
      fastNode = fastNode.getNext();
    }
    Node slowNode = slowSingleNode.getNext();
    while (fastNode != slowNode) {
      if (isFast) {
        fastNode = fastNode.getNext();
      }
      if (fastNode == null) {
        return null;
      }
      fastNode = fastNode.getNext();
      slowNode = slowNode.getNext();
    }
    return fastNode;
  }

  public static void main(String[] args) {
    SingleNode singleNode = LinkFactory.buildSingleNode(1, 2, 3, 4, 5);
    // 存在闭环链表
    singleNode.getNext().getNext().getNext().getNext().setNext(singleNode.getNext());
    System.out.println(isHaveRing(singleNode));
    System.out.println(getRingCutPoint(singleNode).toNodeString());
  }
}
